package _interview100;

import _object.ListNode;

import java.util.ArrayList;

/**
 * 234. 回文链表
 */
public class No234 {
    /**
     * 1.数组集合
     */
    public boolean isPalindrome1(ListNode head) {
        ArrayList<ListNode> arrayList = new ArrayList<>();
        while (head != null) {
            arrayList.add(head);
            head = head.next;
        }
        int left = 0, right = arrayList.size() - 1;
        while (left < right) {
            if (arrayList.get(left++).val != arrayList.get(right--).val) {
                return false;
            }
        }
        return true;
    }

    /**
     * 2.快慢指针 + 翻转链表
     */
    public boolean isPalindrome2(ListNode head) {
        // 快慢指针
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 翻转链表
        ListNode pre = null, cur = slow, nex;
        while (cur != null) {
            nex = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nex;
        }

        // 对比
        while (pre != null) {
            if (head.val != pre.val) {
                return false;
            }
            pre = pre.next;
            head = head.next;
        }

        return true;
    }
}
